package com.azdebugit.niu.ke;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

/*
    此代码来自讨论区 @问心20171127213298 发表的代码,感谢 @问心20171127213298 大大的无私奉献,谢谢!
    本人对其进行了一点注释工作,增加了原代码中的漏掉的一类情形(购买主件和附件二)。
*/

class Item {
    // 价格
    int price;
    // 权重: 价格与重要度的乘积
    int weight;

    public Item(int a, int b) {
        this.price = a;
        this.weight = a * b;
    }
}

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int money = Integer.parseInt(s[0]);
        int amount = Integer.parseInt(s[1]);
        Item[][] items = new Item[amount + 1][3];
        for(int i = 1; i <= amount; i++) {
            s = br.readLine().split(" ");
            int price = Integer.parseInt(s[0]);
            int weight = Integer.parseInt(s[1]);
            int masterID = Integer.parseInt(s[2]);
            Item tmp = new Item(price, weight);
            if(masterID == 0) {
                items[i][0] = tmp;
            } else {
                if(items[masterID][1] == null) {
                    items[masterID][1] = tmp;
                } else {
                    items[masterID][2] = tmp;
                }
            }
        }
        int[] buyable = new int[money + 1];
        for(int i = 1; i <= amount; i++) {
            if(items[i][0] == null) {
                continue;
            }
            for(int j = money; j >= 0; j--) {
                Item master = items[i][0];
                int max = buyable[j];
                if(j >= master.price && max < buyable[j - master.price] + master.weight) {
                    max = buyable[j - master.price] + master.weight;
                }
                if(items[i][1] != null) {
                    int cost = master.price + items[i][1].price;
                    int weight = master.weight + items[i][1].weight;
                    if(j >= cost && max < buyable[j - cost] + weight) {
                        max = buyable[j - cost] + weight;
                    }
                }
                if(items[i][2] != null) {
                    int cost = master.price + items[i][2].price;
                    int weight = master.weight + items[i][2].weight;
                    if(j >= cost && max < buyable[j - cost] + weight) {
                        max = buyable[j - cost] + weight;
                    }
                    cost = master.price + items[i][1].price + items[i][2].price;
                    weight = master.weight + items[i][1].weight + items[i][2].weight;
                    if(j >= cost && max < buyable[j - cost] + weight) {
                        max = buyable[j - cost] + weight;
                    }
                }
                buyable[j] = max;
            }
        }
        System.out.println(buyable[money]);
    }
}